class Solution:
    """前三个正向做的都有问题,这题要反推"""
    def calculateMinimumHP(self, dungeon) -> int:
        dungeon[0][0] = [min(0, dungeon[0][0]), dungeon[0][0]]
        for j in range(1, len(dungeon[0])):
            mid_num = dungeon[0][j - 1][1] + dungeon[0][j]
            dungeon[0][j] = [min(dungeon[0][j - 1][0], mid_num), mid_num]
        for i in range(1, len(dungeon)):
            mid_num = dungeon[i - 1][0][1] + dungeon[i][0]
            dungeon[i][0] = [min(dungeon[i-1][0][0], mid_num), mid_num]
        for i in range(1, len(dungeon)):
            for j in range(1, len(dungeon[0])):
                mid_num = max(dungeon[i - 1][j][1], dungeon[i][j - 1][1]) + dungeon[i][j]
                num = dungeon[i][j]
                dungeon[i][j] = [min(max(dungeon[i-1][j][0], dungeon[i][j-1][0]), mid_num), mid_num]
        # print(dungeon)
        if len(dungeon) == 1 or len(dungeon[0]) == 1:
            return max(-dungeon[-1][-1][0] + 1, 1)
        else:
            mid_num = max(min(dungeon[-2][-1][1] + num, dungeon[-2][-1][0]),
                          min(dungeon[-1][-2][1] + num, dungeon[-1][-2][0]))
            return max(-mid_num + 1, 1)

    def calculateMinimumHP2(self, dungeon) -> int:
        dungeon[0][0] = [min(0, dungeon[0][0]), dungeon[0][0]]
        for j in range(1, len(dungeon[0])):
            mid_num = dungeon[0][j - 1][1] + dungeon[0][j]
            dungeon[0][j] = [min(dungeon[0][j - 1][0], mid_num), mid_num]
        for i in range(1, len(dungeon)):
            mid_num = dungeon[i - 1][0][1] + dungeon[i][0]
            dungeon[i][0] = [min(dungeon[i-1][0][0], mid_num), mid_num]
        for i in range(1, len(dungeon)):
            for j in range(1, len(dungeon[0])):
                num = dungeon[i][j]
                flag = dungeon[i-1][j][0] + dungeon[i-1][j][1] - (dungeon[i][j-1][0] + dungeon[i][j-1][1])
                if flag < 0 or (flag == 0 and dungeon[i-1][j][1] <= dungeon[i][j-1][1]):
                    min_blood_zuo = min(dungeon[i][j - 1][0], dungeon[i][j - 1][1] + dungeon[i][j])
                    dungeon[i][j] = [min_blood_zuo, dungeon[i][j-1][1]+dungeon[i][j]]
                elif flag > 0 or (flag == 0 and dungeon[i-1][j][1] > dungeon[i][j-1][1]):
                    min_blood_shang = min(dungeon[i - 1][j][0], dungeon[i - 1][j][1] + dungeon[i][j])
                    dungeon[i][j] = [min_blood_shang, dungeon[i-1][j][1]+dungeon[i][j]]
        print(dungeon)
        # return max(-dungeon[-1][-1][0] + 1, 1)
        if len(dungeon) == 1 or len(dungeon[0]) == 1:
            return max(-dungeon[-1][-1][0] + 1, 1)
        else:
            mid_num = max(min(dungeon[-2][-1][1] + num, dungeon[-2][-1][0]),
                          min(dungeon[-1][-2][1] + num, dungeon[-1][-2][0]))
            return max(-mid_num + 1, 1)

    def calculateMinimumHP3(self, dungeon) -> int:
        dungeon[0][0] = [min(0, dungeon[0][0]), dungeon[0][0]]
        for j in range(1, len(dungeon[0])):
            mid_num = dungeon[0][j - 1][1] + dungeon[0][j]
            dungeon[0][j] = [min(dungeon[0][j - 1][0], mid_num), mid_num]
        for i in range(1, len(dungeon)):
            mid_num = dungeon[i - 1][0][1] + dungeon[i][0]
            dungeon[i][0] = [min(dungeon[i-1][0][0], mid_num), mid_num]
        for i in range(1, len(dungeon)):
            for j in range(1, len(dungeon[0])):
                mid_num = max(min(dungeon[i-1][j][1] + dungeon[i][j], dungeon[i-1][j][0]),
                              min(dungeon[i][j-1][1] + dungeon[i][j], dungeon[i][j-1][0]))
                flag = dungeon[i - 1][j][0] + dungeon[i - 1][j][1] - (dungeon[i][j - 1][0] + dungeon[i][j - 1][1])
                if flag < 0 or (flag == 0 and dungeon[i - 1][j][1] <= dungeon[i][j - 1][1]):
                    dungeon[i][j] = [mid_num, dungeon[i][j - 1][1] + dungeon[i][j]]
                elif flag > 0 or (flag == 0 and dungeon[i - 1][j][1] > dungeon[i][j - 1][1]):
                    dungeon[i][j] = [mid_num, dungeon[i - 1][j][1] + dungeon[i][j]]
        # print(dungeon)
        return max(-dungeon[-1][-1][0] + 1, 1)

    def calculateMinimumHP4(self, dungeon) -> int:
        dungeon[-1][-1] = max(1, 1-dungeon[-1][-1])
        for j in range(2, len(dungeon[0])+1):
            dungeon[-1][-j] = max(1, dungeon[-1][-j+1] - dungeon[-1][-j])
        for i in range(2, len(dungeon)+1):
            dungeon[-i][-1] = max(1, dungeon[-i+1][-1] - dungeon[-i][-1])
        len_i, len_j = len(dungeon) + 1, len(dungeon[0])+1
        for i in range(2, len_i):
            for j in range(2, len_j):
                # print(dungeon)
                # print(i, j)
                dungeon[-i][-j] = max(1, min(dungeon[-i][-j+1], dungeon[-i+1][-j])-dungeon[-i][-j])
        return dungeon[0][0]

    def calculateMinimumHP5(self, dungeon) -> int:
        dungeon[-1][-1] = min(0, dungeon[-1][-1])
        for j in range(2, len(dungeon[0])+1):
            dungeon[-1][-j] = min(dungeon[-1][-j+1] + dungeon[-1][-j], 0)
        for i in range(2, len(dungeon)+1):
            dungeon[-i][-1] = min(0, dungeon[-i+1][-1] + dungeon[-i][-1])
        for i in range(2, len(dungeon)+1):
            for j in range(2, len(dungeon[0])+1):
                # print(dungeon)
                dungeon[-i][-j] = min(0, max(dungeon[-i][-j+1], dungeon[-i+1][-j])+dungeon[-i][-j])
        return -dungeon[0][0]+1


a = Solution()
# print(a.calculateMinimumHP4([[-2, -3, 3], [-5, -1, 1], [10, 30, -5]]))  # 7
# print(a.calculateMinimumHP4([[-2]]))  # 3
# print(a.calculateMinimumHP4([[-3, 5]]))  # 4
# print(a.calculateMinimumHP4([[1, -4, 5, -99], [2, -2, -2, -1]]))  # 3
# print(a.calculateMinimumHP4([[1, -3, 3], [0, -2, 0], [-3, -3, -3]]))  # 3
# print(a.calculateMinimumHP4([[0, 0, 0], [-1, 0, 0], [2, 0, -2]]))  # 2
# print(a.calculateMinimumHP4([[1, 2, 1], [-2, -3, -3], [3, 2, -2]]))  # 1
# print(a.calculateMinimumHP5([[-2, -3, 3], [-5, -1, 1], [10, 30, -5]]))  # 7
# print(a.calculateMinimumHP5([[-2]]))  # 3
print(a.calculateMinimumHP5([[-3, 5]]))  # 4
# print(a.calculateMinimumHP5([[1, -4, 5, -99], [2, -2, -2, -1]]))  # 3
# print(a.calculateMinimumHP5([[1, -3, 3], [0, -2, 0], [-3, -3, -3]]))  # 3
# print(a.calculateMinimumHP5([[0, 0, 0], [-1, 0, 0], [2, 0, -2]]))  # 2
# print(a.calculateMinimumHP5([[1, 2, 1], [-2, -3, -3], [3, 2, -2]]))  # 1


